package FeatureSelection;
//mrmr feature selection algorithm of Hanchuan Peng
//written by Zehra Cataltepe, May 24, 2011
//Uses the MI code written by Kenan Kule.
//Example usage:
// double [][] xMatrix  ;  //inputs to be filled up 
// double [] labels  ;  //labels to be filled up
//FeatureSelectionmRMRClass mrmr = new FeatureSelectionmRMRClass(xMatrix, labels) ; 
// mrmr.setDiscretize(Boolean.FALSE, 0) ; //by default, there is no discretization
// mrmr.setCriterion(MIDCriterion) ; //default value is MID, you can also choose MIQ
// int[] selectedFeatureIndices = mrmr.mrmrSelect(-1) ; //-1: select all features, k>=1: select k features
// printAr(selectedFeatureIndices) ; //starts from 0.
// printAr(mrmr.getSortedRelevances());  //relevances of the features. TODO: a method to get relevances in the selected order.
// printAr(mrmr.getScores()) ;  //scores for each feature.



import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;

import Analysis.PengMIClass;
import Definitions.NodeClass;
import Global.ConstantVariable;
import Global.DirectoryStructureAndSettingsClass;
import Sampling.SamplingAbstractClass;
import Utility.WorkerUtilityClass;

public class FeatureSelectionmRMRClass {
	private static final double DEFAULT_DISCRETIZE_K = 0.42;
	
	int numberOfFeaturesToSelect = -1;
	public static final int MIDCriterion = 0 ; 
	public static final int MIQCriterion = 1 ; 
	int criterion = MIQCriterion ; 
	private Boolean discretize = Boolean.FALSE ;  //discretize the input features or not. 
	private double discretizeK = DEFAULT_DISCRETIZE_K ; //discretize <mean-k*std=-1, >mean+k*std=1, 0: otherwise
	double relevances[] = null ; 
	double sortedRelevances[] = null ; 
	int relevanceSortedIndices[] = null ; 
	double scores[] = null ; 
	int[] selectedFeaturesIndices = null;
	double[][] xMatrix = null ; 
	double[] labels = null ; 

	public static void printAr(int [] x){
		for (int i=0;i<x.length;i++)
			System.out.print(x[i]+" ") ; 
		System.out.println(); 
	}
	public static void printAr(double [] x){
		for (int i=0;i<x.length;i++)
			System.out.print(x[i]+" ") ; 
		System.out.println(); 
	}
	public static void printMat(double [][] x){
		for (int i=0;i<x.length;i++){
			for (int j=0; j<x[0].length; j++)
				System.out.print(x[i][j]+" ") ; 
			System.out.println(); 
		}
	}
	public static double[] myArrayCopy(double[] x)
	{
		double[] newx = new double[x.length] ; 
		for (int i=0;i<x.length;i++)
			newx[i] = x[i] ;
		return newx ;
	}
	
	//Sorts decreasing, changes x, returns the indices of the elements in sorted order.
	public static int[] mySortDec(double[] x)
	{
		int[] indices = new int[x.length] ; 
		for (int i=0;i<x.length;i++)
			indices[i] = i ; 
		for (int i=0;i<x.length;i++){
			for (int j=i+1;j<x.length;j++){
				if (x[i]<x[j]){
					int tmpint = indices[i] ; 
					indices[i] = indices[j] ; 
					indices[j] = tmpint ; 
					double tmpval = x[i] ; 
					x[i] = x[j] ; 
					x[j] = tmpval ;
				}
			}
		}	
		return indices ;
	}
	
	public static int[] deleteFeature(int[] all, int toDelete)
	{
		int[] remaining = new int[all.length-1] ;
		int k=0 ; 
		for (int i=0;i<all.length;i++)
		{
			if (all[i]!=toDelete){
				remaining[k] = all[i] ; 
				k = k+1 ; 
			}
		}
		return remaining ; 
	}
	
	public static int[] addFeature(int[] all, int toAdd)
	{
		int[] remaining = new int[all.length+1] ; 
		for (int i=0;i<all.length;i++)
		{
				remaining[i] = all[i] ; 
		}
		remaining[remaining.length-1] = toAdd ; 
		return remaining ; 
	}
	
	public static int maxIndx(double[] x){
		int maxIndx = 0 ; 
		double maxValue = x[0] ; 
		for (int i=1;i<x.length;i++){
			if (x[i] > maxValue){
				maxIndx = i ; 
				maxValue = x[i] ; 
			}	
		}
		return maxIndx ; 
	}
	
	public static void discretizeMatrix(double[][] X, double k){
		int d = X[0].length ; 
		double[] meanAr = new double[d] ;
		double[] stdAr = new double[d] ;
		
		for (int i=0; i<d; i++){
			meanAr[i] = 0.0f ; 
			for (int j=0 ; j<X.length ; j++){
				meanAr[i] = meanAr[i] + X[j][i] ; 
			}
			meanAr[i] = meanAr[i]  / X.length ; 		
		}
		for (int i=0; i<d; i++){
			stdAr[i] = 0.0f ; 
			for (int j=0 ; j<X.length ; j++){
				stdAr[i] = stdAr[i] + (X[j][i]-meanAr[i])*(X[j][i]-meanAr[i]) ; 
			}
			stdAr[i] = Math.sqrt(stdAr[i]  / (X.length-1)) ; 		
		}
		for (int i=0; i<d; i++){
			for (int j=0 ; j<X.length ; j++){
				if (X[j][i] < meanAr[i] - k * stdAr[i])
					X[j][i] = -1 ; 
				else if (X[j][i] > meanAr[i] + k * stdAr[i])
					X[j][i] = 1 ; 
				else 
					X[j][i] = 0 ;
			}
		}
	}
	

	FeatureSelectionmRMRClass(double xMatrix[][], double labels[]) 
	{
		this.xMatrix = new double[xMatrix.length][xMatrix[0].length] ; 
		this.labels = new double[labels.length] ; 
		for (int i=0;i<xMatrix.length;i++)
			for (int j=0;j<xMatrix[0].length;j++)
				this.xMatrix[i][j] = xMatrix[i][j] ;
		for (int i=0;i<labels.length;i++)
			this.labels[i] = labels[i] ; 
		
		//mrmrSelect(numberOfFeaturesToSelect );
	}	
	
	public int[] mrmrSelect(int _numberOfFeaturesToSelect)
	{
		if (_numberOfFeaturesToSelect <=0 )
			numberOfFeaturesToSelect = this.xMatrix[0].length ; 
		else
			numberOfFeaturesToSelect = _numberOfFeaturesToSelect ; 
		this.selectedFeaturesIndices = new int[numberOfFeaturesToSelect] ;
		
		if (this.discretize){
			discretizeMatrix(this.xMatrix,discretizeK) ; 
		}
		relevances = PengMIClass.GetCorrelation(this.xMatrix, this.labels);
		
		this.sortedRelevances = myArrayCopy(relevances) ; 
		this.relevanceSortedIndices = mySortDec(this.sortedRelevances) ;
		this.scores = new double[this.numberOfFeaturesToSelect] ; 
		
		this.selectedFeaturesIndices = new int[1] ; 
		this.selectedFeaturesIndices[0] = this.relevanceSortedIndices[0] ; 
		this.scores[0] = this.sortedRelevances[0] ; 
		int[] remainingFeaturesIndices = new int[this.xMatrix[0].length] ; 
		for (int i=0; i<remainingFeaturesIndices.length; i++)
			remainingFeaturesIndices[i] = i ; 
		remainingFeaturesIndices = deleteFeature(remainingFeaturesIndices, this.selectedFeaturesIndices[0]) ;
		for (int i=1; i<this.numberOfFeaturesToSelect; i++){
			//printAr(selectedFeaturesIndices) ;
			
			double[] redundancies = PengMIClass.GetRedundancy(this.xMatrix,remainingFeaturesIndices,selectedFeaturesIndices) ; 
			double[] scoresNow = new double[redundancies.length] ; 
			if (this.criterion==MIDCriterion)
			{
				for (int j=0; j<scoresNow.length; j++)
					scoresNow[j] = relevances[remainingFeaturesIndices[j]]-redundancies[j] ; 
			}
			else{
				for (int j=0; j<scoresNow.length; j++)
					scoresNow[j] = relevances[remainingFeaturesIndices[j]]/redundancies[j] ;
			}
			int selectedFeatureIndx = remainingFeaturesIndices[maxIndx(scoresNow)] ;
			this.selectedFeaturesIndices = addFeature(this.selectedFeaturesIndices,selectedFeatureIndx) ; 
			remainingFeaturesIndices = deleteFeature(remainingFeaturesIndices, selectedFeatureIndx) ;	
			this.scores[i] = scoresNow[maxIndx(scoresNow)] ; 
		}
				
		return this.selectedFeaturesIndices ; 
	}

	
	public int[] getSelectedFeaturesIndices() {
		return selectedFeaturesIndices;
	}
	
	public double[] getSortedRelevances() {
		return this.sortedRelevances;
	}
	
	public double[] getScores() {
		return this.scores;
	}
	
	public void setCriterion(int newCriterion)
	{
		if (newCriterion == MIDCriterion)
			this.criterion = MIDCriterion ; 
		else if (newCriterion == MIQCriterion)
			this.criterion = MIQCriterion ;
		else{
			System.err.println("FeatureSelectionmRMRClass.java:setCriterion, wrong Criterion entered, did not change the criterion.");
		}
	}
	
	public void setDiscretize(Boolean _discretize, double _k){
		this.discretize = _discretize ; 
		if (this.discretize){
			if (_k >0)
				this.discretizeK = _k ; 
			else{
				this.discretizeK = DEFAULT_DISCRETIZE_K ; 
				System.err.println("FeatureSelectionmRMRClass.java: Invalid value of k in setDiscretize method.") ; 
			}
		}
	}
	
	private static void unitTestMRMR1(){
		double [][] xMatrix = null ; 
		double [] labels = null ; 
		try {
			String dirName = Global.ConstantVariable.DefaultDirectoryNamesConstants.DirectoriesUnderStaticRootDirectory.INPUTS_DIRECTORY ; 
			File descFile=DirectoryStructureAndSettingsClass.createFile(dirName, "mrmrtmp.txt");
			FileReader fstream;
			fstream = new 	FileReader(descFile);
			BufferedReader in = new BufferedReader(fstream);
			String strLine;
			int numLines = 0, numColumns = 0 ; 
			String[] words = null ; 

			if ((strLine = in.readLine()) != null)
			{
				words = strLine.split(" ");
				numLines = Integer.parseInt(words[0]) ;
				numColumns = Integer.parseInt(words[1]) ;
				xMatrix = new double[numLines][numColumns-1] ; 
				labels = new double[numLines] ; 
			}
			for (int i=0; i<numLines; i++){
				if ((strLine = in.readLine()) != null)
				{
					words = strLine.split(",");
					labels[i] = Double.parseDouble(words[0]) ; 
					for (int j=0; j<numColumns-1; j++){
						xMatrix[i][j] = Double.parseDouble(words[j+1]) ;
					}
				}
			}
			
		} catch (IOException e) {
			e.printStackTrace();
		}
		FeatureSelectionmRMRClass mrmr = new FeatureSelectionmRMRClass(xMatrix, labels) ; 
		mrmr.setDiscretize(Boolean.FALSE, 0) ; 
		int[] selectedFeatureIndices = mrmr.mrmrSelect(-1) ; 
		printAr(selectedFeatureIndices) ; 
		printAr(mrmr.getSortedRelevances()); 
		printAr(mrmr.getScores()) ; 
	}
	
	private static void unitTestMRMRRandom(){
		Random random = new Random();
		random.setSeed(0);
		
		System.out.println("mrmr Test: ");
		
		int numInstances = 10;
		int numFeatures = 10 ; 
		double [][] xMatrix = new double[numInstances][numFeatures];
		double [] labels = new double[numInstances];
		
		for (int i = 0; i < numInstances; i++) 
		{
			for (int j=0; j<5; j++)
				xMatrix[i][j] = random.nextDouble() ;
			for (int j=5; j<10; j++)
				xMatrix[i][j] = xMatrix[i][j-5] + 0.1*random.nextDouble() ;
			labels[i] = (int) (random.nextDouble()*10) ;
		}
		
		FeatureSelectionmRMRClass mrmr = new FeatureSelectionmRMRClass(xMatrix, labels) ; 
		mrmr.setDiscretize(Boolean.TRUE, 0.42); 
		int[] selectedFeatureIndices = mrmr.mrmrSelect(-1) ; 
		printAr(selectedFeatureIndices) ; 
		
		printMat(xMatrix) ; 
		printAr(labels) ; 

/*		i:0:3 i:1:1 i:2:4 i:3:2 i:4:0 i:5:8 i:6:9 i:7:7 i:8:6 i:9:5 
		0.730967787376657 0.24053641567148587 0.6374174253501083 0.5504370051176339 0.5975452777972018 0.764289627324322 0.2790553341455577 0.7359015793700892 0.6383552569048819 0.6916701957454132 
		0.12889715087377673 0.14660165764651822 0.023238122483889456 0.5467397571984656 0.9644868606768501 0.1393462194988739 0.20911629399307416 0.06431774203299563 0.6243709863259588 1.0635591392483283 
		0.7462414053223305 0.7331520701949938 0.8172970714093244 0.8388903500470183 0.5266994346048661 0.8361749064834799 0.746546054253683 0.8256033112318159 0.9367477840618024 0.598935146523751 
		0.14322038530059678 0.4629578184224229 0.004485602182885184 0.07149831487989411 0.34842022979166454 0.17709735065417215 0.5488934735578876 0.10164030106805647 0.15807290290129794 0.4096783402626514 
		0.21757041220968598 0.8544871670422907 0.009673497300974332 0.6922930069529333 0.7713129661706796 0.28883915502425495 0.8756107045352803 0.08798274627769227 0.7868263308488962 0.7727366016810464 
		0.8537907753080728 0.7860424508145526 0.993471955005814 0.883104405981479 0.17029153024770394 0.9499976671288266 0.8584719541724395 1.0612073711308014 0.9635439477039426 0.21443420761528312 
		0.8528274665994607 0.501834850205735 0.9919429804102169 0.9692699099404161 0.35310607217911816 0.8575540535190737 0.5089972125475151 0.9948537316823804 1.0176369289509262 0.45030108427449267 
		0.7674421030154899 0.5013973510122299 0.2555253108964435 0.30915818724818767 0.8482805002723425 0.7726505568328882 0.5024148964658528 0.29091060786731465 0.31783197276476044 0.9333116517987731 
		0.3078931676344727 0.5316085562487977 0.9188142018385732 0.27721002606871137 0.8742622102831944 0.36888131898574905 0.6224724772184712 0.9232632638542527 0.34188241617260035 0.92394258664546 
		0.5206888198929495 0.36636074451399603 0.47763691175692136 0.7039697053426346 0.3227677982432213 0.5218543037206043 0.4364646383322365 0.5521721977960764 0.7646985301988963 0.34627597082963796 
		2.0 4.0 7.0 1.0 3.0 4.0 9.0 0.0 5.0 3.0*/ 
		/*
		class, f0, f1, f2, f3, f4, f5, f6, f7, f8, f9
		2	, 0.730967787	, 0.240536416	, 0.637417425	, 0.550437005	, 0.597545278	, 0.764289627	, 0.279055334	, 0.735901579	, 0.638355257	, 0.691670196
		4	, 0.128897151	, 0.146601658	, 0.023238122	, 0.546739757	, 0.964486861	, 0.139346219	, 0.209116294	, 0.064317742	, 0.624370986 ,	1.063559139
		7	, 0.746241405	, 0.73315207	, 0.817297071	, 0.83889035	, 0.526699435	, 0.836174906	, 0.746546054	, 0.825603311	, 0.936747784	, 0.598935147
		1	, 0.143220385	, 0.462957818	, 0.004485602	, 0.071498315	, 0.34842023	, 0.177097351	, 0.548893474	, 0.101640301	, 0.158072903	, 0.40967834
		3	, 0.217570412	, 0.854487167	, 0.009673497	, 0.692293007	, 0.771312966	, 0.288839155	, 0.875610705	, 0.087982746	, 0.786826331	, 0.772736602
		4	, 0.853790775	, 0.786042451	, 0.993471955	, 0.883104406	, 0.17029153	, 0.949997667	, 0.858471954 ,	1.061207371	, 0.963543948	, 0.214434208
		9	, 0.852827467	, 0.50183485	, 0.99194298	, 0.96926991	, 0.353106072	, 0.857554054	, 0.508997213	, 0.994853732,	1.017636929	, 0.450301084
		0	, 0.767442103	, 0.501397351	, 0.255525311	, 0.309158187	, 0.8482805	, 0.772650557	, 0.502414896	, 0.290910608	, 0.317831973	, 0.933311652
		5	, 0.307893168	, 0.531608556	, 0.918814202	, 0.277210026	, 0.87426221	, 0.368881319	, 0.622472477	, 0.923263264	, 0.341882416	, 0.923942587
		3	, 0.52068882	, 0.366360745	, 0.477636912	, 0.703969705	, 0.322767798	, 0.521854304	, 0.436464638	, 0.552172198	, 0.76469853	, 0.346275971
*/	
	}
	
	public static FeatureSelectionDataClass unitTestMRMRTestAS(SamplingAbstractClass sampling){

		ArrayList<NodeClass> nodesToBeGivenForFS = sampling.getTrainAndValNodes();
		int size = nodesToBeGivenForFS.size();
		
		int numInstances = size;
		int numFeatures = nodesToBeGivenForFS.get(0).getContentList().get(ConstantVariable.Common_ConstantVariables.DEFAULT_CONTENT_TYPE).getAttributeList().size() ;
		
		System.out.println("mrmr Test AS: :"+ size + "numFeatures:" + numFeatures);
		//System.exit(0);
		
		double [][] xMatrix = new double[numInstances][numFeatures];
		double [] labels = new double[numInstances];
		ArrayList<Double> featuresArrayListOfTheNode;
		double[] featuresArrayOfTheNode;
		
		for (int i = 0; i < size; i++) 
		{
			
			featuresArrayListOfTheNode = nodesToBeGivenForFS.get(i).getContentList().get(ConstantVariable.Common_ConstantVariables.DEFAULT_CONTENT_TYPE).getAttributeList();
			featuresArrayOfTheNode = WorkerUtilityClass.getDoubleArrayFromDoubleArrayList(featuresArrayListOfTheNode);
			System.arraycopy(featuresArrayOfTheNode, 0, xMatrix[i], 0, featuresArrayOfTheNode.length);			
			labels[i] = nodesToBeGivenForFS.get(i).getOrder();
		}
		
		FeatureSelectionmRMRClass mrmr = new FeatureSelectionmRMRClass(xMatrix, labels) ; 
		mrmr.setDiscretize(Boolean.TRUE, 0.42) ; 
		int[] selectedFeatureIndices = mrmr.mrmrSelect(-1) ;
		
		double[] scoresOfTheFeatures = mrmr.getScores();
		
		FeatureSelectionDataClass featureSelectionData = new FeatureSelectionDataClass();		
		featureSelectionData.setSelectedFeaturesIndexes(selectedFeatureIndices, scoresOfTheFeatures);
		
		
		printAr(selectedFeatureIndices) ; 
		
		//printMat(xMatrix) ; 
		//printAr(labels) ; 

/*		i:0:3 i:1:1 i:2:4 i:3:2 i:4:0 i:5:8 i:6:9 i:7:7 i:8:6 i:9:5 
		0.730967787376657 0.24053641567148587 0.6374174253501083 0.5504370051176339 0.5975452777972018 0.764289627324322 0.2790553341455577 0.7359015793700892 0.6383552569048819 0.6916701957454132 
		0.12889715087377673 0.14660165764651822 0.023238122483889456 0.5467397571984656 0.9644868606768501 0.1393462194988739 0.20911629399307416 0.06431774203299563 0.6243709863259588 1.0635591392483283 
		0.7462414053223305 0.7331520701949938 0.8172970714093244 0.8388903500470183 0.5266994346048661 0.8361749064834799 0.746546054253683 0.8256033112318159 0.9367477840618024 0.598935146523751 
		0.14322038530059678 0.4629578184224229 0.004485602182885184 0.07149831487989411 0.34842022979166454 0.17709735065417215 0.5488934735578876 0.10164030106805647 0.15807290290129794 0.4096783402626514 
		0.21757041220968598 0.8544871670422907 0.009673497300974332 0.6922930069529333 0.7713129661706796 0.28883915502425495 0.8756107045352803 0.08798274627769227 0.7868263308488962 0.7727366016810464 
		0.8537907753080728 0.7860424508145526 0.993471955005814 0.883104405981479 0.17029153024770394 0.9499976671288266 0.8584719541724395 1.0612073711308014 0.9635439477039426 0.21443420761528312 
		0.8528274665994607 0.501834850205735 0.9919429804102169 0.9692699099404161 0.35310607217911816 0.8575540535190737 0.5089972125475151 0.9948537316823804 1.0176369289509262 0.45030108427449267 
		0.7674421030154899 0.5013973510122299 0.2555253108964435 0.30915818724818767 0.8482805002723425 0.7726505568328882 0.5024148964658528 0.29091060786731465 0.31783197276476044 0.9333116517987731 
		0.3078931676344727 0.5316085562487977 0.9188142018385732 0.27721002606871137 0.8742622102831944 0.36888131898574905 0.6224724772184712 0.9232632638542527 0.34188241617260035 0.92394258664546 
		0.5206888198929495 0.36636074451399603 0.47763691175692136 0.7039697053426346 0.3227677982432213 0.5218543037206043 0.4364646383322365 0.5521721977960764 0.7646985301988963 0.34627597082963796 
		2.0 4.0 7.0 1.0 3.0 4.0 9.0 0.0 5.0 3.0*/ 
		/*
		class, f0, f1, f2, f3, f4, f5, f6, f7, f8, f9
		2	, 0.730967787	, 0.240536416	, 0.637417425	, 0.550437005	, 0.597545278	, 0.764289627	, 0.279055334	, 0.735901579	, 0.638355257	, 0.691670196
		4	, 0.128897151	, 0.146601658	, 0.023238122	, 0.546739757	, 0.964486861	, 0.139346219	, 0.209116294	, 0.064317742	, 0.624370986 ,	1.063559139
		7	, 0.746241405	, 0.73315207	, 0.817297071	, 0.83889035	, 0.526699435	, 0.836174906	, 0.746546054	, 0.825603311	, 0.936747784	, 0.598935147
		1	, 0.143220385	, 0.462957818	, 0.004485602	, 0.071498315	, 0.34842023	, 0.177097351	, 0.548893474	, 0.101640301	, 0.158072903	, 0.40967834
		3	, 0.217570412	, 0.854487167	, 0.009673497	, 0.692293007	, 0.771312966	, 0.288839155	, 0.875610705	, 0.087982746	, 0.786826331	, 0.772736602
		4	, 0.853790775	, 0.786042451	, 0.993471955	, 0.883104406	, 0.17029153	, 0.949997667	, 0.858471954 ,	1.061207371	, 0.963543948	, 0.214434208
		9	, 0.852827467	, 0.50183485	, 0.99194298	, 0.96926991	, 0.353106072	, 0.857554054	, 0.508997213	, 0.994853732,	1.017636929	, 0.450301084
		0	, 0.767442103	, 0.501397351	, 0.255525311	, 0.309158187	, 0.8482805	, 0.772650557	, 0.502414896	, 0.290910608	, 0.317831973	, 0.933311652
		5	, 0.307893168	, 0.531608556	, 0.918814202	, 0.277210026	, 0.87426221	, 0.368881319	, 0.622472477	, 0.923263264	, 0.341882416	, 0.923942587
		3	, 0.52068882	, 0.366360745	, 0.477636912	, 0.703969705	, 0.322767798	, 0.521854304	, 0.436464638	, 0.552172198	, 0.76469853	, 0.346275971
*/	
		return featureSelectionData;
	}

//public static void Testmrmr() {
	public static void Notmain(String args[]) {
		unitTestMRMRRandom() ; 
		unitTestMRMR1();	
	}

}

